package com.string;

import java.util.ArrayList;
import java.util.List;

/**04-18
 * 分割回文串
 * 递归+回溯
 */
public class Partition131_2 {
    List<List<String>> res = new ArrayList<>();
    List<String> temp = new ArrayList<>();
    public List<List<String>> partition(String s) {
        int len=s.length();

        backTrack(s,0);

        return res;
    }

    private void backTrack(String s, int start) {
        //如果起始位置大于s的大小，说明找到了一组分割方案
        if (start >= s.length()) {
            res.add(new ArrayList(temp));
            return;
        }
        //是回文子串，记录
        for (int i = start; i < s.length(); i++) {
            if (check(s,start,i)){
                String str=s.substring(start,i+1);
                temp.add(str);
            }else {
                continue;
            }
            backTrack(s,i+1);
            temp.remove(temp.size()-1);
        }

    }
    //利用左右指针 判断是否为回文串，
    private boolean check(String s, int left, int right) {
        for (int i = left,j=right; i < j; i++,j--) {
            if (s.charAt(i)!=s.charAt(j)){
                return false;
            }
        }
        return true;
    }
}
